%Carlo Luis M. Bation
%2009-24926
%CMSC 190 Special Problem Proposal
%Note: 
%Processed using TeX maker and MikTeX
\documentclass[journal]{./IEEE/IEEEtran}
\usepackage{cite}
\usepackage{graphicx}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{url}
\usepackage{amsmath}
\usepackage{moreverb}

\newcommand{\SPTITLE}{\bf Waste Truck Routing and Scheduling in \\ Los Ba\~{n}os Laguna 
Using Vehicle Routing Heuristics}
\newcommand{\ADVISEE}{Carlo Luis M. Bation\\\small\BSCS\\\UPLB}
%\newcommand{\ADVISER}{Jaime M. Samaniego}
\newcommand{\BSCS}{Bachelor of Science in Computer Science}
\newcommand{\ICS}{Institute of Computer Science}
\newcommand{\UPLB}{University of the Philippines Los Ba\~{n}os}

        
\markboth{CMSC 190 Special Problem, \ICS}{}
\title{\SPTITLE}
\author{\ADVISEE
}
\pubid{\copyright~2011~ICS \UPLB}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

% TITLE
\maketitle

% INTRODUCTION
\section{Introduction}


\subsection{ Significance of the Study}
The study of waste management involves many fields. One of the main aspects of waste management is waste truck routing and scheduling. It greatly involves graph theory and route optimization on its background. We can say that each stop represents a node and the ways to each node represents the edges in graph theory. Solving the graph problem can lead to route optimization. This leads to the main theme of the study which is to improve scheduling and routing of waste truck in a given area using real world maps.
	
In the Philippines today, usually waste truck management is taken care by government offices and usually by the city of the mayor office. Most don't have a system to schedule the routes of the waste trucks in their area. A routing system is needed in order to minimize cost, manpower and time. It minimizes cost by giving the shortest paths, the minimum way to traverse a group of clients or nodes and this will minimize the usage of gasoline. It also minimizes the possibility the truck to be damage because of the fact that the truck will traverse the minimum route and travel for a short time period. Manpower because we can come up with a solution of minimizing the number of trucks then if the number trucks to be used are minimized, the number of drivers and assistants will also be reduced. The use of time will also be minimized when we consider the weight and type of waste in each node as a parameter. When we know the estimated amount of waste per node the number of going back of the trucks to the depot will be reduce so cost and time here will be reduced.

In foreign countries there is a competition in waste collection. Many companies like SA Waste Holdings, Greenstar and WSN Environmental Solutions competes for customers. One of the factors that can be used as a main weapon on other companies is to have a better way of routing in order to traverse more nodes and to have minimum company expenses in the collection system.
The study also uses the real world maps. So that if a road or something was changed in the topography of the concerned area, the manager will just again run the system and it will produce new results of routes and schedules for the new map.

The map of Los Ba\~{n}os, Laguna will be the first input in the system. This map has interesting routes and has many ways to traverse a given node or place meaning there are more than one way to go to a place. There is also one depot or dump site in the map so the problem will be simplified. The types of garbage in the map also vary. Because of the existence of hospitals in the map, the hospital waste will be included in the constraints of types of wastes. The map also includes the University of the Philippines Los Ba\~{n}os and inside the university there is a building called Physical Science building that produces toxic or chemical waste that is another type of waste. So, not just biodegradable and non-biodegradable types of wastes will be the constraint of the study. 
The focus of this paper is to develop software that can return near optimal routes and schedules for the waste truck to follow. The solutions will be based from vehicle routing heuristics like branch and bound and traveling salesman algorithms. The map of Los Ba\~{n}os, Laguna will be the starting point of the study and other maps will be chosen as input to train the software to be generic and adapt in any kinds of map in the future.

\subsection {Objectives of the Study}

The main objective of this study is to develop software that produces near optimal routes and schedules for waste trucks given an input map from openstreetmap.org. Specifically it aims:
\begin{enumerate}


\item to solve the problem using vehicle routing problem heuristics;

\item to start with the map of Los Ba\~{n}os, Laguna as the first input for the software; 

\item to optimize results using Genetic Algorithm;


\item to make a graphical user interface from the map that can accept inputs from user, examples of inputs are name of the area, weight of garbage in an area and time window for that area;

\item to draw lines connecting the nodes for each truck in the map; and

\item to extend the constraints into heterogeneous trucks meaning that trucks can have different capacities and specifications.

\end{enumerate}

\newpage
\subsection{Date and Place of  Study}

The study will be done at the Institute of Computer Science, College of Art and Science University of the Philippines Los Ba\~{n}os Laguna from October 16, 2011 to January 29, 2012.


\section{Review of Literature}
Waste truck routing and scheduling can be solve using vehicle routing heuristics and other related concepts such the Traveling Problem. Heuristics are those methods that can be program in polynomial time and give results that are near to the optimal solution to the problem. Optimal solution can be achieved in exponential time, meaning as the number of input increases the amount of time also increases exponentially. Heuristics were developed in order to have an acceptable solution to a problem. It runs in polynomial time, meaning as the number of input increases the amount of time only increases linearly. In this part of the paper related literature about waste truck routing and scheduling in terms of combinatorial optimization will be presented.
\subsection{Traveling Salesman Problem}
The first is the Traveling Salesman Problem (TSP). It is based from the 1857 game called Icosian Game invented by Sir William R. Hamilton \cite{dalgety}. The rule of the game is to visit 20 connected points with going to a point only once. We can relate traveling salesman to our problem by making the number of trucks equal to one. It means that the single truck will traverse all nodes or customers.

Branch and Bound algorithm can give a near optimal solution to TSP. The idea of branch and bound algorithm is that you will make a tree.  Find the row minimum of a given matrix of constraints then it will be the starting node of the tree. After finding the row minimum detect the indexes of the matrix that are involve in the row minimum Then compute the different sub tours of the remaining indexes of the matrix and again add the nodes to the parent and repeat the process until an stopping criteria is detected.  Branch and Bound algorithm was first presented by A.H. Land and A.G. Doig in their article \cite{land}.  

Many papers were publish and presentations were made regarding to the solution of TSP using the Branch and Bound Algorithm.  The concept of parallelization was also introduced to make the computation of nodes of the tree in the algorithm \cite{tshoeke}. This is done by assigning different task to each of the processors and because of this the result generation will be fast as like doing the computation in a sequential process with few data. 

A presentation made by Busby, Dodge, Fleming and Negrusa about Backtracking and Branch and Bound algorithm tells how the concept of backtracking helps to know the solution to the TSP in a faster way by implementing some methods related to backtracking. Remember that in Branch and Bound algorithm sometimes if the cost of the current child node is greater than the cost of the previous child nodes then it is needed to go back one higher level in order to come with another better solution and concepts of backtracking can help to find a better path. This is how the combination of backtracking and branch and bound algorithm works: (1) Branch and bound will create the tree of possible paths, (2) as it creates the tree a pointer will check if the current node has the lowest cost (3) then if not a backtracking algorithm will be used and the pointer to the current node will go to another node which have the lowest cost until near optimal path or a stopping criteria is found \cite{busby}.

 An implementation of the said algorithm written in java was made by Pawel Kalczynski in 2005 \cite{kalczynski }.  Pawel made a package of classes in java based from the processes involved in the algorithm and in TSP. Pawel based his package in the Branch and Bound Algorithm made by Balas \cite{balas} .
 
As what we can see solving TSP using Branch and Bound Algorithm requires too much computing power and takes a lot of time. So we need some other methods that can solve TSP in a “serial” way or a simpler way. The paper of Christian Nilsson presents many different heuristics about TSP \cite{nilsson}. One of the methods that were presented was the nearest neighbour algorithm. The idea of this method is to find the nearest accessible node then go to it if it is not yet visited. In waste truck problem with the number of trucks equal to one the starting point is the depot or the garage of the truck and from the depot it will go to the nearest area assigned to it \cite{nilsson}.

\subsection{Vehicle Routing Problem}
The next graph combinatorial problem related to the waste truck routing and scheduling is the vehicle routing problem (VRP). Given number of customers with each having certain demands (time and cost), each customer have distances on each other and each have weights (garbage in terms of waste collection). The goal of the VRP is to (1) minimize the number of vehicles to be use or to optimally use the existing number of vehicles (2) to satisfy the customers by getting the requirements on time and (3) to have a near optimal path to traverse all the customers \cite{garn}.

Vehicle routing problem with time windows (VRPTW) is a type of VRP which added time as a constraint. The idea is that each node or customer has \textit{starting time} and \textit{end time}. The \textit{starting time} is the earliest time the vehicle should arrive to the node and the \textit{ending time} is the latest time the vehicle should arrive to the node.  Solomon on his paper on 1987 lists some heuristics on how to come up with a solution to the VRPTW . One of the heuristics that was presented on the paper is the time oriented nearest neighbour algorithm. The algorithm was similar to the TSP’s nearest neighbour algorithm the VRP version just added the number of vehicles and the time windows as additional constraints. Another heuristic that was presented by Solomon is the insertion heuristic. The goal of the heuristic is to insert a new node that is not yet in the current partial path. The insertion of the new node can be in any part of the partial path and the resulting partial path of the insertion should be feasible \cite{solomon}. 

In terms of waste truck routing not only time windows can be added as a constraint but also the lunch break of the drivers also needs to be consider.  Extension of Solomon’s insertion algorithm was made so that a better time window handling will be done and to have an optimal lunch break for the drivers \cite{byung}.

Another constraint that can be added to the problem is the number of available vehicles that already existed. The problem here is that what if the number of vehicles available where not yet sufficient in order to have the optimal path for waste collection so some customers will be not served. Holding list is used to store customers that were not served in the resulting path. Maximization of customers into the vehicles was made so that all customers will be served. Tabu search was used to insert customers in a vehicle schedule. Tabu search is an enhanced version of local search. It uses data structures to store all visited candidate solutions to avoid repetition in searching \cite{hoong}.

Evolutionary methods such as genetic algorithm and coevolutionary genetic algorithm approach can be used in solving VRP \cite{machado}. These methods can come up with better solutions than normal heuristics. Both algorithms came from the concept of genetics in science mainly the theory of evolution of Charles Darwin. The algorithm can be simply describe in this steps: (1) generate possible solutions (2) evolve this solutions to new set of solutions (3) loop until a stopping criteria is found.The solutions will evolve as the given constraints changes. The coevolutionary genetic algorithm add some heuristics, like nearest neighbour algorithm, to generate some of the possible solutions while the simple genetic algorithm uses random possible solutions at the starting phase of the genetic algorithm. So the result of the coevolutionary genetic algorithm is nearer to the optimal solution than the result of the simple genetic algorithm.

\subsection{Open Street Map (osm)}
In this study we will use the data generated by Open Street Map (http://www.openstreetmap.org/) an open source online mapping system. In Open Street Map you can convert a given map into xml and download it. This xml file have attributes like \textit{lat }(latitude) and \textit{long}(longitude) that can be used into knowing the position of a place in the map this is from. In the Philippines there are two websites that are using Open Street Map as their mapping service for their users. Those are Ortigas Online and Red Cross Rizal Chapter. The Wikipedia page (http://wiki.openstreetmap.org/)  of Open Street Map is the source for this data.
\subsection{Ending Marks}
Traveling Salesman Problem algorithms are essential for path finding and can help solving the problem with the number of trucks is equal to one. Vehicle Routing Problem with Time Windows algorithms are essential for routing with capacity and time as main constraints. The basics and some applications of openstreetmap is essential in order to have a real world nodes represented by the places in the given map. These concepts can help me accomplish my objectives in this study.

\section{Methodology}
\subsection{Data Gathering and Research}
In order to have more knowledge in the technologies and algorithms that will be used in solving this problem plenty of research is needed. The technologies that will be used is the openstreetmap.org for the map and xml input and java as the main programming language. The algorithms that will be used are the nearest neighbour algorithm, assignment algorithm and genetic algorithm. 

\subsection{Parsing the \textit{\textbf{osm}} File}
The \textit{osm} file is the input of the user that can be downloaded at openstreetmap.org. The user will enter this \textit{osm} file to the parser of the system. The parser will convert the \textit{osm} file, which is in \textit{xml} (extensible mark-up language) format, to usable inputs for the problem. The \textit{xml} file has different tags that denote a particular element like nodes, ways, longitude, latitude and other elements in the map. This elements specially the nodes and ways are the main element for creating the graph.

\subsection{Rendering the \textit{osm} File and the User Interface.}

To have a personalized view, rendering the \textit{osm} file and combining the data that was collected in the parsing part is needed. User interface will be shown in this phase where the user can pinpoint nodes that he/she wants to service. In the user interface there is a spinner that lets the user to enter the number of trucks the user wants to use. The minimum number of truck is one and the maximum is ten. 

The user interface includes the creation of the buttons, combo boxes or selection boxes and the design of the interface of the system.  The creation of these elements is for the user to interact to the system and to put the user's inputs to the system.

Figure 1 shows a simple user interface of a prototype for the program and uses Nearest Neighbour Algorithm as the solver. 

\begin{figure}[h]
\begin{center}
\includegraphics[height=60mm,width=100mm]{screenshotNNAlgo.png}
\caption{Sample User Interface with Nearest Neighbour Algorithm as Solver}
\end{center}
\end{figure}

\subsection{Conversion to Graph Problem.}

The user will tag a node that he/she wants to service. This tagging system will enclose the selected node into a rectangle. Then because of the rectangle represent each node the system can now get the distances of each rectangle to other rectangles and store it into a list of distances of the rectangles or nodes. Using this code snippet: 

\begin{verbatim}

Math.sqrt(((x-x1) * (x-x1)) 
		+ ((y-y1) * (y-y1)));

\end{verbatim}

the system now can compute for the distances of each rectangle in the map. The programming language java owned by Oracle has a Rectangle class that is suitable for the tagging system. The language also has the Math class for the computation of the distances of the nodes. 
Solving the Graph problem.

Using the nearest neighbour algorithm with a simple truck assignment we can get a solution to our problem. The computation will always start with the depot or the 0th element in the matrix. The system will compute the shortest path using the nearest neighbour algorithm.
The nearest neighbour algorithm steps are: (1) from the depot select the nearest node to it.
 (2) Go to that node if it is not visited yet but if it is visited then find another near node to the previous node. (3) Store the selected node to the list of visited nodes. (4) 
Repeat step one until all nodes are covered.

\subsection{Assigning the Nodes in Each of the Truck}
After solving the shortest path assign each node in the list of visited nodes in each truck. The assigning technique is simple. First divide the number of nodes by the number of trucks. Then the quotient will be the number of nodes that will be assigned in a truck.  If there is a remainder then assign them equally in each truck. The assignment will be based on the order of the nodes in the list of visited nodes. To give a better look for this algorithm here is an example. In case the resulting list of visited nodes is [0 ,3, 4, 2, 1] where \textit{0} is the depot and there are two trucks then the assignments for each truck are for truck A [0, 3, 4] and for truck B [0, 2, 1]. 

Another example is if there is a remainder. For example the resulting list of visited nodes is [0, 5, 3, 4, 2, 1] and the number of trucks is 2. There is a remainder which is one. The assignment will be for truck A the nodes are [0, 5, 3, 4] and for truck B the nodes are [0, 2, 1]. Each remainder was assigned to the truck that have the route nearest to the depot so that if it's capacity of carrying garbage exceeds because of the added remainder node to it, then it can go back to the depot to dump it's garbage then go back to the node that is not serviced yet.
Optimizing the path using the genetic algorithm.

\subsection{Genetic Algorithm}
After finding a solution using the nearest neighbour algorithm the next step is to optimize the path by using the principles of genetic algorithm.


The first step of the algorithm is the generation of the initial population of possible solution. For our problem half of the population will be generated randomly and half of the population will be generated using the modification of nearest neighbour algorithm. The modification of the nearest neighbour algorithm is to include other short paths. Meaning the second shortest path, the third short path up to the \textit{nth} short path. The random part of the population will be the permutation of the number of nodes.

Then calculate the fitness of each path or chromosome (chromosome is the term in genetic algorithm that means a possible solution to the problem). The fitness function considers the minimum value of the distance travel by each truck and also considers the estimated capacities of each truck for the given chromosome. The fitness of each path is their cost plus the cost if the path is divided in each of the trucks. Here is a code snippet of the \textbf{\textit{Fitness}} class in java:
\begin{verbatim}

class Fitness {

public void getFitness(Path p, Truck t){

	p.fitness = this.summationCost(Path.nodes) 
	
				+ this.summationCostPerTruck(Path,t);
	
}
...
}
\end{verbatim}
Here we look at the method \textit{getFitness} with the parameters p which is an object of the class Path and t from the class Truck. The method \textit{summationCost} just compute the summation of the cost of the distance of each node of the path in their succeeding node. The algorithm of the \textit{summationCostPerTruck} method is at the \textit{Assigning the Nodes in Each of the Truck} section of this paper.

Next step is the selection where the system selects the fittest chromosomes and kills all weak chromosomes. For this research the fitness of each chromosome will be sorted and the weak half of the population will be disregarded. The list of cost of the paths will be sorted and the low half part of the structure will be eliminated.

The fifth step is the crossover part where we combine two parent paths to form a new path or a child. The formation of a \textit{child} is done by order crossover. For a clear view here is an example of order crossover.  Let P1 be the path [1,2,5,3,4,7,6] and P2 be the path [2,4,7,5,3,1,6]. Suppose that P1's cost is smaller than P2's cost so select P1 as the path that will be the reference path. Randomly select two index of P1, let i = 1 and j = 3. Let C be the resulting child of P1 and P2. Copy the nodes from P1(1) up to P1(3) to C so that C(1) = P1(1), C(2) = P1(2) and C(3) = P1(3). Then C(4) should be equal to P2(4) but since the value of P2(4) is already in C we shift to P2(5) so C(4) = P2(5). Repeat this process until C is constructed.  Note that i should be greater than or equal to 1 and less than the size of P1. See Table 1 for a good look of the data \cite{karova} \cite{prins} \cite{chang}.

\begin{table}[h]
\caption{Example of Order Crossover Operation by Prins} %title of the table
\centering % centering table
\begin{tabular}{c rrrrrrr} % creating eight columns
\hline % inserts single-line
\\
		&  & i & & j & & & \\
\hline
Index   & 0 & 1 & 2 & 3 & 4 & 5 & 6\\ % Entering row contents
P1      & 1 & 2 & 5 & 3 & 4 & 7 & 6\\
P2      & 2 & 4 & 7 & 5 & 3 & 1 & 6\\
\hline
\\
C		& 7 & 2 & 5 & 3 & 1 & 6 & 4\\[1ex] 
\hline
\end{tabular}
\label{tab:hresult}
\end{table}

A mutation step can be added as a sixth step to improve the generation of the children. The mutation operator will be based on Christian Prins algorithm \cite{prins}. The mutation algorithm is a local search. Before applying this local search the child should be a possible solution to the problem. Then let u and v be a node or a depot and can be in the same path or distinct path. Then let x be the successor of u and y be the successor of v in a path. The following moves according to Prins should be implemented to the path of the child:
\begin{itemize}
\item Move 1: if u is a client node, move u after v,

\item Move 2: if u and x are client nodes, move (u, x) after v,

\item Move 3: if u and x are client nodes, move (x, u) after v,

\item Move 4: if u and v are client nodes, permute u and v,
\item Move 5: if u, x and v are clients nodes, permute (u, x) with v,

\item Move 6: if (u, x) and (v, y) are client nodes, permute (u, x) and (v, y),

\item Move 7: if (u, x) and (v, y) are non-adjacent in the same trip, replace them by (u, v) and (x, y)

\item Move 8: if (u, x) and (v, y) are in distinct trips, replace them by (u, v) and (x, y),

\item Move 9: if (u, x) and (v, y) are in distinct trips, replace them by (u, y) and (x, v).


\end{itemize}
The process of moving should be done until no saving can be generated or the change is the fitness of the new path is not changing in a big way. The new child will be added if it's fitness is better than the worst child in the population \cite{prins} \cite{chang}.

Stop if the fitness is not changing in a great way or stop if the indicated number of generations where achieved else use the newly generated population then repeat the second step up to the sixth step.

\subsection{Plotting and Printing of the Results}
After finding the near optimal path given by the system it is time to plot the resulting path for each truck in the map. The trucks will have different colours in terms of lines that will be plotted in the map. There is also a text file that contains the path and the node assignment for each truck. The \textit{way} element of the \textit{osm} file will be the guide for drawing route lines for each of the truck. 
Figure 1 in subsection C shows an example of result. In the figure the red square is the depot while the blue squares are the nodes or customer to be serviced. In the figure there are two lines with different colours representing the number of trucks the user gave which is two.

Figure 2 shows the plotting of nodes when the number of truck is equal to 1. Here the concepts of traveling salesman was used.
\begin{figure}[h]
\begin{center}
\includegraphics[height=60mm,width=100mm]{screenshotNNAlgoTSP.png}
\caption{Truck number is 1 with Nearest Neighbour Algorithm as Solver}
\end{center}
\end{figure}


Figure 3 shows the plotting of nodes when the number of truck is equal to 3. Here the concepts of vehicle routing problem with the assignment of m-number of truck was used.
\begin{figure}[h]
\begin{center}
\includegraphics[height=60mm,width=100mm]{screenshotNNAlgoVRP.png}
\caption{Truck number is 3 to One with Nearest Neighbour Algorithm as Solver}
\end{center}
\end{figure}


% BIBLIOGRAPHY
\bibliographystyle{./IEEE/IEEEtran}
\bibliography{./draftproposalBib}

\end{document}
